[[abstract]]Given a sequence A of numbers and two positive integers l-script and k, we study the problem to find k disjoint segments of A, each has length at least l-script , such that their sum of densities is maximized. We give the first known polynomial-time algorithm for the problem: For general k, our algorithm runs in O(n l-script k] time. For the special case with k = 2 (respectively, k = 3), we also show how to solve the problem in O(n) (respectively, O(n + l-script 2)} time.
展开▼
